package com.carl.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by carlXie on 2016/3/9.
 */
public class LetterCombinations {
    private static String[] digitStrings = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public static void main(String[] args) {
        List<String> list = letterCombinations("23");

        for(String str: list) {
            System.out.println(str);
        }

    }
    public static List<String> letterCombinations(String digits) {

        List<String> resultList = new ArrayList<String>();

        getNext(digits, "", resultList);

        return resultList;
    }

    private static List<String> getNext(String digits, String str, List<String> list) {
        int digitsLen = digits.length();
        String digitString = digitStrings[digits.charAt(0) - 48];
        int stringLen = digitString.length();


        if (digitsLen == 1) {
            for (int i = 0; i < stringLen; i++) {
                list.add(str + digitString.charAt(i));
            }
            return list;
        }

        for (int i = 0; i < stringLen; i++) {
            getNext(digits.substring(1), str + digitString.charAt(i), list);
        }
        return list;

    }
}
